LPN operations

Learning Parity with Noise functions for PVAC-HFHE encryption

The LPN module implements the Learning Parity with Noise primitive used for pseudorandom function evaluation in PVAC-HFHE.

Core functions

prf_R()

Evaluates the main pseudorandom function to generate a randomizer element.

Fp prf_R(const PubKey& pk, const SecKey& sk, const RSeed& seed)

pk · const PubKey&

Public key containing system parameters

sk · const SecKey&

Secret key containing PRF keys and LPN secret

seed · const RSeed&

Seed containing ztag and 128-bit nonce

return · Fp

A nonzero field element in the prime field

This function computes three independent LPN evaluations and multiplies them together for enhanced security. It uses domain separators PRF_R1, PRF_R2, and PRF_R3.

prf_R_noise()

Evaluates the noise pseudorandom function.

Fp prf_R_noise(const PubKey& pk, const SecKey& sk, const RSeed& seed)

pk · const PubKey&

Public key containing system parameters

sk · const SecKey&

Secret key containing PRF keys and LPN secret

seed · const RSeed&

Seed containing ztag and 128-bit nonce

return · Fp

A nonzero field element representing cryptographic noise

Similar to prf_R() but uses noise-specific domain separators (PRF_NOISE1, PRF_NOISE2, PRF_NOISE3) for domain separation.

prf_R_core()

Core LPN evaluation function used internally.

Fp prf_R_core(
    const PubKey& pk,
    const SecKey& sk,
    const RSeed& seed,
    const char* dom
)

pk · const PubKey&

Public key containing system parameters

sk · const SecKey&

Secret key containing PRF keys and LPN secret

seed · const RSeed&

Seed for deterministic randomness

dom · const char*

Domain separator string for cryptographic separation

return · Fp

A nonzero field element derived from LPN evaluation

Evaluation process

1. Generate LPN response - Computes y = As + e where:

   • A is a random matrix derived from the seed
   • s is the LPN secret from the secret key
   • e is Bernoulli noise with parameter tau = lpn_tau_num/lpn_tau_den

2. Apply Toeplitz hash - Uses a Toeplitz matrix multiplication to compress the LPN output to 127 bits

3. Hash to field - Maps the 127-bit output to a nonzero field element

lpn_make_ybits()

Generates the LPN response vector y = As + e.

void lpn_make_ybits(
    const PubKey& pk,
    const SecKey& sk,
    const RSeed& seed,
    const char* dom,
    std::vector<uint64_t>& ybits
)

pk · const PubKey&

Public key containing LPN parameters lpn_n, lpn_t, lpn_tau_num, lpn_tau_den

sk · const SecKey&

Secret key containing the LPN secret bits lpn_s_bits

seed · const RSeed&

Seed for generating the random matrix

dom · const char*

Domain separator string

ybits · std::vector<uint64_t>&

Output parameter receiving the computed bit vector (length lpn_t bits)

Algorithm

For each row r = 0 to lpn_t - 1:

1. Generate random row vector from PRG
2. Compute dot product with secret: dot = row · s
3. Generate noise bit: e = 1 with probability tau, else e = 0
4. Set output bit: y[r] = dot ⊕ e

The noise parameter tau = lpn_tau_num / lpn_tau_den determines the noise rate. Default is tau = 1/8.

Cryptographic primitives

derive_aes_key()

Derives an AES-256 key and nonce from the secret key and seed.

void derive_aes_key(
    const PubKey& pk,
    const SecKey& sk,
    const RSeed& seed,
    const char* dom,
    uint8_t out_key[32],
    uint64_t& out_nonce
)

pk · const PubKey&

Public key (used for canon_tag and H_digest)

sk · const SecKey&

Secret key containing PRF keys

seed · const RSeed&

Seed for key derivation

dom · const char*

Domain separator string

out_key · uint8_t[32]

Output buffer for 256-bit AES key

out_nonce · uint64_t&

Output parameter for the derived nonce

The key is derived using SHA-256 over:

• The 4 PRF keys from the secret key
• The public key’s canon_tag
• The H matrix digest
• The seed’s ztag and nonce
• The domain separator hash

hash_to_fp_nonzero()

Maps 127 bits to a nonzero field element.

Fp hash_to_fp_nonzero(uint64_t lo, uint64_t hi)

lo · uint64_t

Lower 64 bits

hi · uint64_t

Upper 63 bits (most significant bit should be 0)

return · Fp

A nonzero field element in constant time

If the input is zero, returns the field element 1 using constant-time masking to prevent timing attacks.

fnv1a_domain()

Computes a 64-bit hash of a domain separator string.

uint64_t fnv1a_domain(const char* dom)

dom · const char*

Null-terminated domain separator string

return · uint64_t

64-bit FNV-1a hash

Uses the FNV-1a algorithm for fast, non-cryptographic hashing of domain separators.

AES-CTR implementation

AesCtr256

Hardware-accelerated AES-256 in counter mode.

struct AesCtr256 {
    void init(const uint8_t key[32], uint64_t nonce);
    uint64_t next_u64();
    void fill_u64(uint64_t* out, size_t n);
    uint64_t bounded(uint64_t M);
};

Methods

init · void(const uint8_t[32], uint64_t)

Initialize the cipher with a 256-bit key and 64-bit nonce

next_u64 · uint64_t()

Generate the next 64-bit pseudorandom value

fill_u64 · void(uint64_t*, size_t)

Fill an array with n pseudorandom 64-bit values

bounded · uint64_t(uint64_t)

Generate a uniformly random value in [0, M) without bias

This implementation requires AES-NI support. The library will fail to compile without -maes or -march=native on x86_64.

Security parameters

The default LPN parameters provide:

• Information-theoretic bound: 2226 bits
• Classical security: 200+ bits
• Quantum security: 100+ bits

These estimates assume:

• lpn_n = 4096 (secret dimension)
• lpn_t = 16384 (number of samples)
• tau = 1/8 (noise rate)

The triple evaluation in prf_R() and prf_R_noise() amplifies security beyond a single LPN call.

Example usage

#include <pvac/crypto/lpn.hpp>

using namespace pvac;

PubKey pk;
SecKey sk;
RSeed seed = { ztag, make_nonce128() };

// Evaluate PRF
Fp r = prf_R(pk, sk, seed);

// Evaluate noise PRF
Fp noise = prf_R_noise(pk, sk, seed);

// Both r and noise are nonzero field elements

Related functions

• toep_127() - Toeplitz matrix hashing
• keygen() - Generates LPN secret during key generation